P là một tập hợp con của NP (tập hợp các bài toán giải được trong thời gian đa thức bởi máy Turing bất định). Mặc dù chưa được chứng minh, nhiều chuyên gia tin rằng P là tập con thực sự của NP.

P bao hàm NL, lớp các bài toán giải được trong không gian bộ nhớ O ( log ⁡ n ) {\displaystyle O(\log n)} bởi máy Turing bất định.